// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.interval_tree;
import java.util.NoSuchElementException;
import java.util.Stack;

import static java.lang.Math.max;



// Интервальное дерево (см. Кормен «Алгоритмы. Построение и анализ»)
// для отрезков целых чисел включающих обе границы.
// Основано на красно-черном дереве с использованием дополнительной информации
// в узлах, обновляемой при вставке (поэтому не изпользуется java.util.Tree...).
// Операция вставки выполняется за O(lg n).
// Дерево поддерживает сжатие: объединение пересекающихся узлов.
// Поиск не поддерживается данным типом, для выполнения операции необходимо
// вызвать метод compile, создающий объект, оптимизированный под поиск.
public class IntervalTree implements Iterable<IntInterval>, Cloneable {
  // Итератор по интервалам дерева, предоставляющий возможнсть проверки
  // соблюдения свойств красно-черного дерева в отладочных целях.
  // Интервалы возращаются в порядке возрастания левой границы.
  public class Iterator implements java.util.Iterator<IntInterval> {
    public void remove() { throw new UnsupportedOperationException(); }
    public boolean hasNext() { return !next_.isNil(); }
    public IntInterval next() {
      if ( !hasNext() ) { throw new NoSuchElementException(); }

      final IntInterval result = next_.key();
      if ( hasRightChild() ) {
        moveRight();
      } else if ( !stack_.empty() ) {
        moveUpTo(stack_.pop());
      } else {
        next_ = Node.nil;
      }
      return result;
    }


    Iterator() {
      if ( !root_.isNil() ) {
        moveLeft();
      }
      black_height_ = current_black_height_;
    }


    // Проверка соблюдения свойств красно-черноо дерева для _данного_ узла:
    // если узел корневой: проверка того, что он черный;
    // если узел красный: проверка того, что родитель — черный;
    // если узел листовой, проверка того, что черная высота дерева для данного
    // узла совпадает с черной высотой дерева полученной по левому пути.
    // Так как данное дерево является интервальным, то помимо указанных
    // выше свойств должны выполняться должны выполняться следующее:
    // поле additional должно быть максимумом от additional дочерных
    // и правой границей текущего узла.
    boolean checkRequirements() {
      if ( next_ == root_ && next_.isRed() ) { return false; }

      if ( next_.isRed() && next_.parent().isRed() ) { return false; }

      if ( !hasLeftChild() && !hasRightChild() &&
           current_black_height_ != black_height_ ) { return false; }

      if ( next_.additional() < next_.key().max() ) { return false; }

      if ( hasLeftChild() &&
          next_.child(left_).additional() > next_.additional()) {
        return false;
      }

      if ( hasRightChild() &&
           next_.child(right_).additional() > next_.additional() ) {
        return false;
      }
      return true;
    }


    private boolean hasLeftChild() { return !next_.child(left_).isNil(); }
    private boolean hasRightChild() { return !next_.child(right_).isNil(); }


    // Циклический спуск к листому узлу по всем левым дочерним.
    private void moveLeft() {
      while ( hasLeftChild() ) {
        stack_.push(next_);
        next_ = next_.child(left_);

        if ( next_.isBlack() ) {
          current_black_height_++;
        }
      }
    }

    // Спуск к правому доченему узлу (алгоритм TREE_SUCCESSOR).
    private void moveRight() {
      assert hasRightChild();

      next_ = next_.child(right_);

      if ( next_.isBlack() ) {
        current_black_height_++;
      }
      moveLeft();
    }

    // Циклический подъем по родительским узлам до заданного.
    private void moveUpTo(final Node node) {
      while ( next_ != node ) {
        if ( next_.isBlack() ) {
          current_black_height_--;
        }
        next_ = next_.parent();
      }
    }


    // Узел, который будет возвращен следующим вызовом next().
    private Node next_ = root_;
    private int current_black_height_ = 0;

    private final Stack<Node> stack_ = new Stack<Node>();

    private final int black_height_;
    private static final boolean left_ = true;
    private static final boolean right_ = false;
  }


  public static void main(final String [] args) {
    final IntervalTree t = new IntervalTree();
    assert !t.compile().contains(0);
    assert t.toString().isEmpty();

    t.insert(new IntInterval(16,21));
    t.insert(new IntInterval(8,9));
    t.insert(new IntInterval(5,8));
    t.insert(new IntInterval(0,3));
    t.insert(new IntInterval(6,10));
    t.insert(new IntInterval(15,23));
    t.insert(new IntInterval(25,30));
    t.insert(new IntInterval(17,19));
    t.insert(new IntInterval(19,20));
    t.insert(new IntInterval(31,31));
    assert "(0,3) (5,8) (6,10) (8,9) (15,23) (16,21) (17,19) (19,20) (25,30) (31,31)".equals(t.toString());

    t.shrink();
    assert "(0,3) (5,10) (15,23) (25,31)".equals(t.toString());


    final IntervalSearchSet bs_is = t.compile();
    t.insert(new IntInterval(665, 666));
    assert "(0,3) (5,10) (15,23) (25,31) (665,666)".equals(t.toString());

    final IntervalSearchSet t_is = t.compile();
    assert t.checkRbtRequirements();

    // getPrev нужен только для assert, который проверяет корректность итератора.
    IntInterval prev = t.iterator().next();
    for ( final IntInterval i : t ) {
      assert prev.min() <= i.min();
      prev = i;
    }

    final IntervalSearchSet[] iss = { bs_is, t_is };
    assert "0 1 2 3 5 6 7 8 9 10 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31".equals(bs_is.toString());
    assert "0 1 2 3 5 6 7 8 9 10 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 665 666".equals(t_is.toString());

    for ( final IntervalSearchSet is : iss ) {
      assert !is.contains(-1000000);
      assert !is.contains(-1);
      assert is.contains(0);
      assert is.contains(1);
      assert is.contains(3);
      assert !is.contains(4);
      assert is.contains(15);
      assert is.contains(19);
      assert is.contains(23);
      assert !is.contains(24);
      assert is.contains(26);
      assert is.contains(30);
      assert is.contains(31);
      assert !is.contains(32);

      int p = is.iterator().next() - 1;
      for ( final int i : is ) {
        assert p < i;
        p = i;
        System.out.printf("%d ", i);
      }
    }

    assert !t_is.contains(664);
    assert t_is.contains(665);
    assert t_is.contains(666);
    assert !t_is.contains(667);

    System.out.printf("\n%s", t.toDot());
  }


  public Iterator iterator() {
    return new Iterator();
  }


  public boolean isEmpty() {
    return root_.isNil();
  }

  public int size() {
    int result = 0;
    for ( final IntInterval i : this ) {
      result++;
    }
    return result;
  }


  // Представление дерева на языке dot.
  public String toDot() {
    if ( root_.isNil() ) { return ""; }

    final StringBuilder sb = new StringBuilder();
    sb.append("digraph interval_tree {\n");
    root_.toDot(sb);
    sb.append("}");
    return sb.toString();
  }

  // Генерация строки, содержащей все интервалы в порядке возрастания
  // вида: "(1,2) (3,4) (666,900)".
  public String toString() {
    if ( root_.isNil() ) { return ""; }

    final StringBuilder sb = new StringBuilder();
    for ( final IntInterval i : this ) {
      sb.append(i);
      sb.append(' ');
    }
    sb.setLength(sb.length() - 1);  // удаление последнего пробела
    return sb.toString();
  }


  // Добавление нового интервала в дерево.
  // Время работы: O(lg n).
  public void insert(final IntInterval i_key) {
    final Node z = new Node(i_key);
    final boolean left = true;
    final boolean right = !left;

    Node y = Node.nil;
    Node x = root_;

    while ( !x.isNil() ) {
      y = x;
      if ( less(z, x) ) { x = x.child(left); }
      else { x = x.child(right); }
    }

    z.setParent(y);
    if ( y.isNil() ) { root_ = z; }
    else if ( less(z, y) ) { y.setChild(left, z); }
    else { y.setChild(right, z); }

    z.setChild(left, Node.nil);
    z.setChild(right, Node.nil);
    z.colorRed();
    fixMaxUpToRoot(z);

    insertFixUp(z);
    isShrunk_ = false;  // уже не может гарантировать ужатость.
    assert checkRbtRequirements();
  }


  // Сжатие дерева, путем объединения интервалов, для которых это возможно.
  // Метод строит новое дерево и заменяет корень данного на построенный.
  // Время работы: O(n lg n), повторный вызов ничего не делает, если между
  // вызовами не производилась операция вставки.
  // @warning Метод инвалидирует итераторы.
  public void shrink() {
    if ( isShrunk_ ) { return; }
    if ( root_.isNil() ) { return; }

    final IntervalTree shrunk = new IntervalTree();
    IntInterval prev = iterator().next();

    // Возможно, следует проверять необходимость создания нового дерева
    // возможно оно будет эквивалентно текущему, но такая операция занимает
    // O(n), в то время как построение нового O(n lg n) — не сильно дольше.
    for ( final IntInterval cur : this ) {
      if ( canBeMerged(prev, cur) ) {
        prev = merge(prev, cur);
      } else {
        shrunk.insert(prev);
        prev = cur;
      }
    }
    shrunk.insert(prev);
    assert shrunk.checkRbtRequirements();
    root_ = shrunk.root_;
    isShrunk_ = true;
  }


  // Создание интервльного множества — объекта, оптимизированного для
  // операций поиска, а не вставки.
  // Метод предварительно ужимает дерево: объединяет соседние интервалы
  // в один, если это возможно. Это позволяет уменьшить дерево и размер
  // выходного множества (в некоторых случаях особенно сильно).
  // В зависимости от размера метод возвращает разные структуры данных
  // с общим интерфейсом IntervalSearchSet.
  // Время работы: O(n lg n), повторный вызов: O(n), если между вызовами
  // не производилась операция вставки.
  // @warning Метод инвалидирует итераторы.
  public IntervalSearchSet compile() {
    if ( root_.isNil() ) { return new BitSetIntervalSearchSet(0,0); }

    shrink();

    final int min = iterator().next().min();
    final int max = root_.additional();
    final int size = max - min + 1;

    // Если общее число элементов во всех интервалах дерева невелико имеет
    // смысл заменить его на битовую маску. Число 128 выбрано как размер
    // таблицы ASCII (точнее количество печатных символов — около 70),
    // выровненный до числа, кратного 64.

    if ( size > 128 ) {
      return new TreeIntervalSearchSet(root_.clone());
    }

    final BitSetIntervalSearchSet r = new BitSetIntervalSearchSet(min, size);
    for ( final IntInterval ii : this ) {
      for ( final Integer i : ii ) {
        r.add(i);
      }
    }
    return r;
  }


  // Восстановаление свойтв красно-черного дерева после операции вставки.
  // Время работы: O(lg n).
  private void insertFixUp(final Node i) {
    Node z = i;
    while ( z.parent().isRed() ) {
      final boolean left = z.parent() == z.parent().parent().child(true);
      final boolean right = !left;

      final Node y = z.parent().parent().child(right);
      if ( y.isRed() ) {
        z.parent().colorBlack();
        y.colorBlack();
        z.parent().parent().colorRed();
        z = z.parent().parent();
      } else {
        if ( z == z.parent().child(right) ) {
          z = z.parent();
          rotate(z, left);
        }
        z.parent().colorBlack();
        z.parent().parent().colorRed();
        rotate(z.parent().parent(), right);
      }
    }
    root_.colorBlack();
  }

  // Поворот относительно узла x. Направление поворота зависит от флага to_left.
  // Время работы: O(1).
  private void rotate(final Node x, final boolean to_left) {
    final boolean left = to_left;
    final boolean right = !left;

    final Node y = x.child(right);
    x.setChild(right, y.child(left));

    if ( !y.child(left).isNil() ) {
      y.child(left).setParent(x);
    }

    y.setParent(x.parent());

    if ( x.parent().isNil() ) { root_ = y; }
    else if ( x == x.parent().child(left) ) { x.parent().setChild(left, y); }
    else { x.parent().setChild(right, y); }

    y.setChild(left, x);
    x.setParent(y);

    fixMax(x);
    fixMax(y);
  }


  // Проверка условия упорядоченности по возрастанию узлов lhv и rhv.
  // Время работы: O(1).
  private static boolean less(final Node lhv, final Node rhv) {
    return lhv.key().compareTo(rhv.key()) < 0;
  }


  // Вычисление additional для узла n, как максимума между additional его
  // дочерних узлов и правой границей его интервала.
  // Время работы: O(1).
  private static int countAdditional(final Node n) {
    final int n1m = n.key().max();
    final int n2m = n.child(true).isNil() ? n1m : n.child(true).additional();
    final int n3m = n.child(false).isNil() ? n1m : n.child(false).additional();
    return Math.max(Math.max(n1m, n2m), n3m);
  }

  // Вычисление значения поля additional для узла z.
  // Поле содержит максимальное значение от additional дочерних узлов и
  // правой границы интервала узла z: z.key().max().
  // Время работы: O(1).
  private static void fixMax(final Node z) {
    z.setAdditional(countAdditional(z));
  }

  // Исправление поля additional у всех предков узла n.
  // Время работы: O(lg n).
  private void fixMaxUpToRoot(final Node n) {
    for ( Node z = n ; z != root_ ; z = z.parent() ) {
      fixMax(z);
    }
    fixMax(root_);
  }


  // Проверка выполнения свойства красно-черного дерева для данного объекта.
  // Метод используется в отладочных целях.
  // Время работы: O(n).
  private boolean checkRbtRequirements() {
    for ( final Iterator i = iterator() ; i.hasNext() ; i.next() ) {
      if ( !i.checkRequirements() ) {
        return false;
      }
    }
    return true;
  }


  // Проверка пересечения двух интервалов с учетом l.compareTo(r) <= 0.
  // Примеры: (1,3) и (2,5) или (1,3) и (3,5).
  // Время работы: O(1).
  private static boolean overlaps(final IntInterval l, final IntInterval r) {
    assert l.compareTo(r) <= 0;
    return l.min() <= r.min() && r.min() <= l.max();
  }

  // Проверка соприкосновения двух интервалов (т.е. минимум правого на единицу
  // больше максимума левого) с учетом lh.compareTo(r) <= 0.
  // Пример: (1,3) и (4,5).
  // Время работы: O(1).
  private static boolean touches(final IntInterval l, final IntInterval r) {
    assert l.compareTo(r) <= 0;
    return l.max() + 1 == r.min();
  }

  // Проверка возможности объединения двух интервалов (то есть проверка
  // непустоты их пересечения), причем l.compareTo(r) <= 0.
  // Время работы: O(1).
  private static boolean canBeMerged(final IntInterval l, final IntInterval r) {
    assert l.compareTo(r) <= 0;
    return overlaps(l, r) || touches(l, r);
  }

  // Слияние двух интервалов в один с учетом lh.compareTo(r) <= 0.
  // @pre canBeMerged(l, r).
  // Время работы: O(1).
  private static IntInterval merge(final IntInterval l, final IntInterval r) {
    assert l.compareTo(r) <= 0;
    assert canBeMerged(l, r);
    return new IntInterval(l.min(), max(l.max(), r.max()));
  }


  // Корневой узел дерева.
  private Node root_ = Node.nil;

  // Флаг установлен в ИСТИНУ, когда данное дерево ужато, то есть ни один
  // интервал не может быть объединен.
  private boolean isShrunk_ = true;
}




// Узел дерева IntervalTree.
// Для обобщения алгоритмов, использующих данную стрктуру данных,
// доступ к дочерних узлам осуществляется на основе флага, что позволяет
// при необходимости инвертировать алгоритм (т.е. обращаться не к левому,
// а правому потомку), что сокращает размер кода в 2 раза.
class Node implements Cloneable {
  public Node clone() {
    try {
      final Node n = (Node)super.clone();
      n.key_ = (IntInterval)key_.clone();

      if ( left_.isNil() ) {
        n.left_ = Node.nil;
      } else {
        n.left_ = left_.clone();
        n.left_.parent_ = n;
      }

      if ( right_.isNil() ) {
        n.right_ = Node.nil;
      } else {
        n.right_ = right_.clone();
        n.right_.parent_ = n;
      }

      return n;
    }
    catch(CloneNotSupportedException e) {
      assert false;
      return null;
    }
  }

  void toDot(final StringBuilder sb) {
    assert !isNil();

    sb.append('"');
    sb.append(key_);
    sb.append('"');
    sb.append(" [ label = \"{ ");
    sb.append(key_);
    sb.append(" | ");
    sb.append(additional_);
    sb.append(" }\"");
    if ( is_red_ ) { sb.append(" fillcolor = red"); }
    else {sb.append(" fillcolor = black color = white fontcolor = white"); }

    sb.append(" shape = Mrecord style = filled");
    sb.append(" width = 1 height = 0.75 fixedsize = true ]; ");

    if ( !left_.isNil() ) {
      sb.append('"');
      sb.append(key_);
      sb.append('"');
      sb.append(" -> ");
      sb.append('"');
      sb.append(left_.key_);
      sb.append('"');
      sb.append("; ");
    }
    if ( !right_.isNil() ) {
      sb.append('"');
      sb.append(key_);
      sb.append('"');
      sb.append(" -> ");
      sb.append('"');
      sb.append(right_.key_);
      sb.append('"');
      sb.append("; ");
    }
    sb.append('\n');

    if ( !left_.isNil() ) { left_.toDot(sb); }
    if ( !right_.isNil() ) { right_.toDot(sb); }
  }


  static Node makeNil() { return new Node(); }

  Node(final IntInterval key) {
    parent_ = Node.nil;
    left_ = Node.nil;
    right_ = Node.nil;
    is_red_ = true;
    key_ = key;
  }


  IntInterval key() { return key_; }

  void setParent(final Node parent) { parent_ = parent; }
  Node parent() { return parent_; }

  // Получение ссылки на дочерний узел в зависимости от переданного флага:
  //  - true: левый
  //  - false: правый.
  Node child(final boolean is_left) { return is_left ? left_ : right_; }
  void setChild(final boolean is_left, final Node child) {
    if ( is_left ) { left_ = child; }
    else { right_ = child; }
  }

  boolean isRed() { return is_red_; }
  boolean isBlack() { return !is_red_; }
  void colorRed() { assert !isNil(); is_red_ = true; }
  void colorBlack() { assert !isNil(); is_red_ = false; }

  int additional() { return additional_; }
  void setAdditional(final int additional) { additional_ = additional; }

  boolean isNil() { return parent_ == null; }

  private Node() { key_ = new IntInterval(-1, -1); }


  // Nil-узел, используемый в качестве родителя корневого узла
  // и дочерних узлов листовых.
  static final Node nil = Node.makeNil();

  private /*final*/ IntInterval key_;
  private Node parent_;
  private Node left_;
  private Node right_;
  private boolean is_red_;
  private int additional_;
}

